package com.LeeCode;

import java.util.HashSet;

/**
 * 使数组元素互不相同所需的最少操作次数
 */

public class Code3396 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 2, 3, 3, 5, 7};
        System.out.println(new Code3396().minimumOperations(nums));
    }

    public int minimumOperations(int[] nums) {
        int ans = minimumOperations(nums, 0, nums.length - 1);
        return ans;
    }

    public int minimumOperations(int[] nums, int start, int end) {

        if (check(nums, start, end)) { // 检查是否满足条件，若无重复则无需操作
            return 0;
        } else if (end - start > 2) {  // 递归两种情况
            return Math.min(minimumOperations(nums, start + 3, end), minimumOperations(nums, start, end - 3)) + 1;
        } else {
            return 1; // 数量不足三个且不满足条件
        }
    }

    public boolean check(int[] nums, int start, int end) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = start; i <= end; i++) {
            if (!set.contains(nums[i])) {
                set.add(nums[i]);
            } else {
                return false;
            }
        }
        return true;
    }
}
